1. Field of the Invention
The present invention generally relates to halftoning techniques in printers and, more particularly, to a system and method to correct for the actual shape of the printer dots with the correction being propagated so that the error management is consistent with the rationale of error diffusion methods.
2. Description of the Prior Art
Most printers today can print in only a limited number of colors. Halftoning consists in printing a picture (or more generally displaying it on some two-dimensional medium) with small dots in a limited number of colors such that it appears to consist of many colors when viewed from some distance. For example, a picture of black and white dots can appear to display grey levels when viewed from some distance.
Error diffusion, as first described in "An Adaptive Algorithm for Spatial Greyscale" by R. W. Floyd and L. Steinberg in Proceeding of the SID 17/2, (1976) pp. 75-77, is a popular technique for halftoning used today and is considered to be one of the best, and the best among the techniques with similar operating time. This technique and others are reviewed in the book Digital Halftoning, MIT Press, Cambridge, Ma. 1987, by R. Ulichney which is a general reference for digital halftoning.
The operation of error diffusion basically spreads the error occurring at a given pixel across neighboring pixels. The spreading of the error is described by an ordered set of numbers called filter coefficients forming together an error filter. At each point, the input image data is combined with the diffused error and a printing decision is made according to some threshold.
After Floyd and Steinberg, other filters were proposed, in particularly by J. F. Jarvis, C. N. Judice and W. H. Ninke in "A Survey of Techniques for the Display of Continuous Tone Pictures on Bilevel Displays", Computer Graphics and Image Processing, Vol. 5, (1976) pp. 13-40, and by P. Stucki in "MECCA--A Multiple-Error Correction Computation Algorithm for Bi-Level Image Hardcopy Reproduction", IBM Res. Rep., RZ1060 (1981). Error diffusion has been further enriched, for instance by
varying the threshold, in order to cluster dots or to reduce artifacts, for instance in "Halftoning Techniques Using Error Correction", Proceedings of the SID, Vol. 27/4 (1986) pp. 305-308, by G. S. Fawcett and G. F. Schrack, in U.S. Pat. No. 5,055,942 to R. L. Levien, in U.S. Pat. No. 5,150,429 to R. L. Miller and C. M. Smith, or in U.S. Pat. No. 5,325,211 to R. Eschbach, and varying the filter according to grey regions and compensating for the problems hereby introduced, in order to reduce artifacts, for instance in "Computer-generated Holograms with Pulse-density Modulation", J. Opt. Soc. A1 (1984) pp. 5-10, by R. Hauck and O. Bryngdhal, or in "Reduction of Artifacts in Error Diffusion by Means of Input-dependent Weights", J. El. Imag. 2(4) (1993) pp. 352-358, by R. Eschbach. PA1 For each site (i,j) where A operates, a list L(i,j) of neighbors of (i,j) where A has already operated. The set L(i,j) for the preferred embodiment is shown shaded in FIG. 1. PA1 For each (k,l) in L(i,j), a coefficient c(i-k,j-l) where we have expressed that the coefficient only depends on (i-k) and (j-l) (in fact, in most cases, only on .vertline.i-k.vertline. and .vertline.j-l.vertline. or on (i-k).sup.2 +(j-l).sup.2). PA1 A matrix of states S, defined by setting S(i,j) equal to G(i,j) minus the sum of the errors at all (k,l)s in L(i,j) weighted by the coefficients c(k-i,l-j), the error E(k,l) at (k,l) being computed as the difference S(k,l)-sign(S(k,l)). Here sign is the signum function (sign(x)=-1 if x&lt;0, sign(x)=1 otherwise). PA1 1. The amount of black has to be taken account of at the pixel where it occurs, PA1 2. The corrections due to dot shape and size have to be propagated in order to preserve the logics of error diffusion, and PA1 3. Either the correction of the error has to be complete or one should be able to estimate how much error is left to decide on a trade-off between completeness of the correction and computational time. PA1 a matrix D of printing decisions (no action or print a black dot at (i,j)) (which is already necessary for some error diffusion methods defined for other purposes), PA1 a matrix V of actual areas in each pixel covered by black ink, (where -1 stands for no ink, 1 stands for the entire pixel being covered with ink, 0 stands for half of the surface of the pixel being covered with ink, and so on), and PA1 a matrix I taking account of which dots, at or near (i,j), contributed to the black ink at site (i,j). PA1 1. accurate bookkeeping (everywhere) of the matrices D, V, and I, and PA1 2. bookkeeping of the error matrix E, so that it is accurate enough (alternatively, bookkeeping of the state matrix S is done and E is obtained via the expression E=S-V). In contrast to V, and I which are corrected everywhere, the matrix E (or alternatively S) is corrected PA1 either only on a list of neighbors which are affected by printing decisions at (i,j) AND are close enough to (i,j) (i.e., N(i,j).orgate.M(i,j), or PA1 everywhere as needed for complete propagation of the corrections.
Since there are several error diffusion algorithms, we use a general presentation to define them. For simplicity, we will discuss only the case of black and white pictures, but the discussion and our invention apply to color pictures as well. In the sequel, all matrices considered together have the same arbitrary size. With G standing for a matrix of grey levels defining a greyscale picture, a digital halftoning method is a G-independent algorithm A which defines a matrix M of white and black dots with the purpose of imitating G as closely as possible, in terms of giving an as close as possible visual impression. We will assume the picture is described on a square grid, although other types of grids such as hexagonal grids are also possible.
For standard error diffusion algorithms, defining A includes the following ingredients:
We assume that the grey levels are represented by a number between -1 and 1, with -1 indicating white and 1 indicating black. With these ingredients, the formulas defining an error diffusion algorithm read ##EQU1## A threshold t is added to the standard algorithm, which may depend on several ingredients in several ways and can either be constant or vary from point to point.
Stucki already considered the problem of compensating for actual black dot sizes and shapes in error diffusion, which is important since the basic method assumes square black and white dots of the same size. Error diffusion makes it harder to calibrate according to printer performances than passive dithering methods, as discussed for instance in "Measurement of Printer Parameters for Model-based Halftoning", J. El. Imag., 2(3) (1993), pp. 193-204, by T. N. Pappas, C. K. Dong, and D. I. Neuhoff, or in "Measurement-based Evaluation of a Printer Dot Model for Halftone Algorithm Tone Correction", J. El. Imag., 2(3) (1993), pp. 205-212, by C. J. Rosenberg, making it preferable to use model-based error diffusion as described for instance in "Printer Models and Error Diffusion", IEEE Transactions on Image Processing, 4(1) (1995), pp. 66-80, by T. N. Pappas and D. L. Neuhoff, or in "A modified error-based error diffusion", IEEE Signal Processing Letters, 4(2) (1997), pp. 36-38, by Y. Lin and T. C. Ko.